# -*- coding: utf-8 -*-

"""剑指 Offer II 109. 开密码锁
一个密码锁由 4 个环形拨轮组成，每个拨轮都有 10 个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。
每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，请给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

示例 1:
输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，因为当拨动到 "0102" 时这个锁就会被锁定。

示例 2:
输入: deadends = ["8888"], target = "0009"
输出：1
解释：
把最后一位反向旋转一次即可 "0000" -> "0009"。

示例 3:
输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：
无法旋转到目标数字且不被锁定。

示例 4:
输入: deadends = ["0000"], target = "8888"
输出：-1

提示：
1 <= deadends.length <= 500
deadends[i].length == 4
target.length == 4
target 不在 deadends 之中
target 和 deadends[i] 仅由若干位数字组成"""

from queue import Queue

class Solution:
    """建模如下：
    将4个滚轮的一个数字状态看作一个顶点，其转动一个滚轮能到的下一个数字状态为两个顶点的边，是一个无向图。
    每个数字只能与8个数字建立边的关系，可以发现这是一个稀疏图，可以用邻接表来实现。
    同时在构图的时候，顺便排查死亡数字，使死亡数字不存在图中。
    寻找最短路径，就是用广度搜索来实现。
    
    在正式代码实现的时候，发现在建图过程中便可以利用广度优先的思路，将最短路径给出来，都不用建图"""

    @staticmethod
    def turn_roller(num):
        digits = []
        i = 0
        while i < 4:
            digits.append(num % 10)
            num = num // 10
            i += 1

        digits.reverse()

        # print(digits)

        ladder = {0: (1, 9), 1: (2, 0), 2: (3, 1), 3: (4, 2), 4: (5, 3), 5: (6, 4), 6: (7, 5), 7: (8, 6), 8: (9, 7), 9: (0, 8)}

        follows = []
        follows.append(ladder[digits[0]][0]*1000 + digits[1]*100 + digits[2]*10 + digits[3])
        follows.append(ladder[digits[0]][1]*1000 + digits[1]*100 + digits[2]*10 + digits[3])
        follows.append(digits[0]*1000 + ladder[digits[1]][0]*100 + digits[2]*10 + digits[3])
        follows.append(digits[0]*1000 + ladder[digits[1]][1]*100 + digits[2]*10 + digits[3])
        follows.append(digits[0]*1000 + digits[1]*100 + ladder[digits[2]][0]*10 + digits[3])
        follows.append(digits[0]*1000 + digits[1]*100 + ladder[digits[2]][1]*10 + digits[3])
        follows.append(digits[0]*1000 + digits[1]*100 + digits[2]*10 + ladder[digits[3]][0])
        follows.append(digits[0]*1000 + digits[1]*100 + digits[2]*10 + ladder[digits[3]][1])

        return follows


    def openLock(self, deadends: list, target: str) -> int:
        deadends = set([int(i) for i in deadends])
        if 0 in deadends:
            return -1

        target = int(target)

        if target == 0:
            return 0

        begin = 0
        visited = set()
        que = Queue()
        dist = [0,]*10000

        que.put(begin)
        visited.add(begin)
        dist[begin] = 0
        success = False

        while (not success) and (not que.empty()):
            x = que.get()
            follows = self.turn_roller(x)
            for y in follows:
                if y in deadends:
                    continue
                if y in visited:
                    continue
                que.put(y)
                visited.add(y)
                dist[y] = dist[x] + 1

                if y == target:
                    success = True
                    break

        if success:
            return dist[target]
        else:
            return -1

if __name__ == '__main__':
    print(Solution().openLock(deadends = ["0201","0101","0102","1212","2002"], target = "0202"))
    print(Solution().openLock(deadends = ["8888"], target = "0009"))
    print(Solution().openLock(deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"))
    print(Solution().openLock(deadends = ["0000"], target = "8888"))
